package NC93_设计LRU缓存结构;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    static class Node{
        int key, val;
        Node pre;
        Node next;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);   
    private int k;  // 缓存大小
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.k = k;
        head.next = tail;
        tail.pre = head;

        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count(); // 获取数组中开头为 2(get操作) 的元素个数
        int[] res = new int[len];

        for (int i = 0, j = 0; i < operators.length; i++){
            if (operators[i][0] == 1){  // 获取数组中开头为 1(set操作) 的元素个数
                set(operators[i][1], operators[i][2]);  // set(key, val)
            }else { // 获取数组中开头为 2(get操作) 的元素个数
                res[j++] = get(operators[i][i]);    // get(key)
            }
        }
        return res;
    }

    private void set(int key, int val) {
        // 判断是否存在 key
        Node node = null;
        if (map.containsKey(key)){  // 如果已经存在 key， 将 val 更新，并删除这个节点，再将 node 插入到表头
            node = map.get(key);
            node.val = val;
            // 删除该结点
            node.next.pre = node.pre;
            node.pre.next = node.next;
            // 将 node 结点提到第一个
            moveToFirst(node);
        }else { // 如果不存在 key，先判断是否超出空间，如果超出先在链表和map删除最后一个结点，再将结点插入到表头，并将对应的映射添加到map中
            if (map.size() == k){
                // 在 map 中删除映射到最后一个结点的 key
                int keyRemove = tail.pre.key;
                map.remove(keyRemove);
                // 在链表中删除最后一个结点
                tail.pre.pre.next = tail;
                tail.pre = tail.pre.pre;
            }
            node = new Node(key, val);
            // 在 map 中添加对新节点的映射
            map.put(key, node);
            // 将结点插入到表头
            moveToFirst(node);
        }
    }

    private void moveToFirst(Node node) {
        head.next.pre = node;
        node.next = head.next;
        node.pre = head;
        head.next = node;
    }

    private int get(int key){
        // 如果不存在，返回 -1
        // 如果存在 key， 先将 node结点 删除，然后再将此节点插入到链表的表头
        if (!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        // 删除结点
        node.next.pre = node.pre;
        node.pre.next = node.next;
        // 插入表头
        moveToFirst(node);
        return node.val;
    }
}
